#include "string.h"
#ifndef __LIB_H
#define __LIB_H
typedef unsigned size_t;
// 非完整stdlib.h

int atoi(const char *str)
{
    int sum = 0;
    while (*str >= '0' && *str <= '9')
    {
        sum = sum * 10 + (*str - '0');
        str++;
    }
    return sum;
}
int atol(const char *str)
{
    long sum = 0;
    while (*str >= '0' && *str <= '9')
    {
        sum = sum * 10 + (*str - '0');
        str++;
    }
    return sum;
}

#pragma region MemoryControl
struct MemoryBlock {
    bool available; 
    size_t size;
};
void *HEAP_STRAT = 0x00000;
void *HEAP_END = 0x00000;
// 需要调查
void free(void *ptr)
{
    MemoryBlock *free;
    free = (MemoryBlock* ) ptr - sizeof(MemoryBlock); // 找到该内存块的控制信息的地址
    free->available = 1;  // 该空间置为可用
    // 查找下一个内存空间，如果可用，则合并
    MemoryBlock *next_block = free+free->size+sizeof(MemoryBlock);
    while(next_block->available){
        
        free->size += next_block->size + sizeof(MemoryBlock);
        next_block = free+free->size+sizeof(MemoryBlock);
    }
    return;
}
void *malloc(size_t size)
{
        void *current_location;  // 当前访问的内存位置
    MemoryBlock *current_location_mcb;  // 只是作了一个强制类型转换
    void *memory_location;  // 这是要返回的内存位置。初始时设为
                            // 0，表示没有找到合适的位置
    // 要查找的内存必须包含内存控制块，所以需要调整 numbytes 的大小
    size_t numbytes = numbytes + sizeof(MemoryBlock);
    // 初始时设为 0，表示没有找到合适的位置
    memory_location = 0;
    /* Begin searching at the start of managed memory */
    // 从被管理内存的起始位置开始搜索
    // managed_memory_start 是在 malloc_init 中通过 sbrk() 函数设置的
    current_location = HEAP_STRAT;
    while (current_location != HEAP_END) {
        // current_location 是一个 void 指针，用来计算地址；
        // current_location_mcb 是一个具体的结构体类型
        // 这两个实际上是一个含义
        current_location_mcb = (struct MemoryBlock *)current_location;
        if (current_location_mcb->available) {
            if (current_location_mcb->size >= numbytes) {
                // 找到一个可用、大小适合的内存块
                current_location_mcb->available = 0;  // 设为不可用
                memory_location = current_location;      // 设置内存地址
                if(current_location_mcb->size != numbytes){
                    // 分割内存
                    // 新分割的内存块的起始位置
                    void* new_location = current_location + numbytes + sizeof(MemoryBlock);
                    // 新分割的内存块的大小
                    size_t new_size = current_location_mcb->size - numbytes - sizeof(MemoryBlock);
                    // 新分割的内存块的元信息
                    struct MemoryBlock* new_mcb = (MemoryBlock*)new_location;
                    new_mcb->available = 1;
                    new_mcb->size = new_size;
                }
                break;
            }
        }
        // 否则，当前内存块不可用或过小，移动到下一个内存块
        current_location = current_location + current_location_mcb->size;
    }
    // 循环结束，没有找到合适的位置，需要向操作系统申请更多内存
    if (!memory_location) {
        // 扩展堆
        // 新的内存的起始位置就是 last_valid_address 的旧值
        memory_location = HEAP_END;
        // 将 last_valid_address 后移 numbytes，移动到整个内存的最右边界
        HEAP_END += numbytes;
        // 初始化内存控制块 mem_control_block
        current_location_mcb = (MemoryBlock*)memory_location;
        current_location_mcb->available = 0;
        current_location_mcb->size = numbytes;
    }
    // 最终，memory_location 保存了大小为 numbyte的内存空间，
    // 并且在空间的开始处包含了一个内存控制块，记录了元信息
    // 内存控制块对于用户而言应该是透明的，因此返回指针前，跳过内存分配块
    memory_location = memory_location + sizeof(MemoryBlock);
    // 返回内存块的指针
    return memory_location;

}
void *calloc(size_t n, size_t size)
{
    malloc(n * size);
}

void *realloc(void *ptr, size_t size)
{
    void* newptr = malloc(size);
    memcpy(newptr, ptr, size);
    free(ptr);
    return newptr;
}
#pragma endregion
template <typename T>
void swap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
}
#endif